package com.realtest.baidu;

import java.util.Arrays;

/**
 * @Author: Ethan Yankang
 * @Program: Interview
 * @Date: 2024-08-24 23:35
 **/
public class MaxElementDP {
    public static void main(String[] args) {

//        int[] nums=new int[]{3,4,5,2,4,1,0};
        int[] nums=new int[]{1,1,1,1,1,1,1,1};
                System.out.println("原来的数组:");
                System.out.println(Arrays.toString(nums));

                //Do Something
                DPSolve(nums);
                System.out.println("之后的数组:");
                System.out.println(Arrays.toString(nums));
    }

    private static void DPSolve(int[] nums) {
        int[] dpMax=new int[nums.length];
        int[] dpMin=new int[nums.length];
//        dpMax[j]代表位置大于j的所有元素的最大值
        dpMax[nums.length-1]=nums[nums.length-1];
        for (int i = nums.length-2; i >=0; i--) {
            dpMax[i]=Math.max(nums[i], dpMax[i+1]);
        }
//        dpMax[j]代表位置大于j的所有元素的最小值
        dpMin[nums.length-1]=nums[nums.length-1];
        for (int i = nums.length-2; i >=0; i--) {
            dpMin[i]=Math.min(nums[i], dpMin[i+1]);
        }
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]<dpMax[i+1]){
                nums[i]=dpMin[i+1];
            }else {
                nums[i]=-1;
            }
        }
        nums[nums.length-1]=-1;
    }
}

